package uhaleks;

/**
 * Класс Двунаправленный связный список
 *
 * @version 1.0       05.07.2014, 06.07.2014
 * @author            Александр Уханов
 */

public class LinkedList<E> {
    protected Node<E> header; // header.next - ссылка на первый элемент; header.prev - последний
    protected int size;

    /** Добавляет указанный элемент в конец этого списка */
    public void add(E e) {
        if (size == 0) {
            header = new Node<E>(null, null, null);
            header.next = header.prev = header;
        }
        Node<E> newNode = new Node<E>(header.prev, e, header);
        newNode.prev.next = newNode;
        newNode.next.prev = newNode;
        size++;
    }

    /** Добавляет указанный элемент в "середину" этого списка */
    public void add(int index, E e) {
        Node<E> n = entry(index);
        Node<E> newNode = new Node<E>(n.prev, e, n);
        newNode.prev.next = newNode;
        newNode.next.prev = newNode;
        size++;
    }

    /** Удаляет элемент в указанной позиции в этом списке */
    public E remove(int index) {
        return RemoveNode(entry(index));
    }

    /** Удаляет и возвращает первый элемент из этого списка */
    public E removeFirst() {
        return RemoveNode(header.next);
    }

    /** Удаляет и возвращает последний элемент из этого списка */
    public E removeLast() {
        return RemoveNode(header.prev);
    }

    protected E RemoveNode(Node<E> n) {
        E result = n.item;
        n.prev.next = n.next;
        n.next.prev = n.prev;
        n.next = n.prev = null;
        n.item = null;
        size--;
        return result;
    }

    /** Поиск элемента с указанным индексом */
    protected Node<E> entry(int index) {
        if (index < 0 || index >= size)
            throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size);
        Node<E> e = header;
        if (index < (size >> 1))
            for (int i = 0; i <= index; i++)
                e = e.next;
        else
            for (int i = size; i > index; i--)
                e = e.prev;
        return e;
    }

    /** Добавляет указанный элемент в конец этого списка */
    public void addLast(E e) {
        add(e);
    }

    /** Добавляет указанный элемент в начало этого списка */
    public void addFirst(E e) {
        add(0, e);
    }

    //* Возвращает количество вхождений элементов определенного значения в список */
    public int count(E e) {
        Node<E> n = header;
        int c = 0;
        for (int i = 0; i < size; i++) {
            n = n.next;
            if (e == n.item)
                c++;
        }
        return c;
    }

    //* Возвращает элемент по заданной позиции этого списка */
    public E get(int index) {
        return entry(index).item;
    }

    //* Возвращает первый элемент этого списка */
    public E getFirst() {
        return header.next.item;
    }

    //* Возвращает последний элемент этого списка */
    public E getLast() {
        return header.prev.item;
    }

    /** Возвращает количество элементов в этом списке */
    public int size() {
        return size;
    }

    /** Возвращает true, если список пуст */
    public boolean empty() {
        if (size == 0)
            return true;
        else
            return false;
    }

    protected static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
}
